#include <pthread.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <semaphore.h>

#define NUM_PHILOSOPHER 5
#define NUM_TAKE 3

bool chopstick[NUM_PHILOSOPHER];

int task[4];
sem_t task_request_sem;
sem_t task_reply_sem;
pthread_mutex_t task_lock;

int ask_waiter(int philosopher, int hand, int take) {
    pthread_mutex_lock(&task_lock);
    task[0] = philosopher;
    task[1] = hand;
    task[2] = take;
    sem_post(&task_request_sem);
    sem_wait(&task_reply_sem);
    int result = task[3];
    pthread_mutex_unlock(&task_lock);
    return result;
}


void end_waiter() {
    pthread_mutex_lock(&task_lock);
    task[0] = -1;
    task[1] = -1;
    task[2] = -1;
    sem_post(&task_request_sem);
    pthread_mutex_unlock(&task_lock);
}


void take_chopstick(int number, int hand) {
    while (true) {
        if (ask_waiter(number, hand, 1) == 0) {
            chopstick[number] = false;
            break;
        }
    }
}

void put_chopstick(int number, int hand) {
    while (true) {
        if (ask_waiter(number, hand, 0) == 0) {
            chopstick[number] = true;
            break;
        }
    }
}

void *philosopher(void *arg) {
    int philosopher_id = *(int*)arg;
    for (int i = 0; i < NUM_TAKE; i++) {
        printf("philosopher %d is thinking\n", philosopher_id);
        sleep(1);
        take_chopstick(philosopher_id, 0);
        take_chopstick(philosopher_id, 1);
        printf("philosopher %d is eating\n", philosopher_id);
        sleep(1);
        put_chopstick(philosopher_id, 0);
        put_chopstick(philosopher_id, 1);
    }
    return NULL;
}

void *waiter(void *arg) {
    int chopstick_taked[NUM_PHILOSOPHER];
    memset(chopstick_taked, -1, sizeof(int) * NUM_PHILOSOPHER);

    int philosopher;
    int hand;
    int take;
    bool valid;

    while (true) {
        sem_wait(&task_request_sem);
        philosopher = task[0];
        hand = task[1];
        take = task[2];
        valid = false;

        if (take == 1) {
            valid = chopstick_taked[(philosopher + hand) % NUM_PHILOSOPHER] == -1 && (chopstick_taked[(philosopher + hand ^ 1) % NUM_PHILOSOPHER] == -1 || chopstick_taked[(philosopher + hand ^ 1) % NUM_PHILOSOPHER] == philosopher);
            if (valid) {
                chopstick_taked[(philosopher + hand) % NUM_PHILOSOPHER] = philosopher;
            }
        } else if (take == 0) {
            valid = true;
            chopstick_taked[(philosopher + hand) % NUM_PHILOSOPHER] = -1;
        } else {
            break;
        }

        task[3] = valid ^ 1;
        sem_post(&task_reply_sem);
    }
    return NULL;
}


int main() {
    sem_init(&task_request_sem, 0, 0);
    sem_init(&task_reply_sem, 0, 0);
    pthread_mutex_init(&task_lock, NULL);

    memset(chopstick, 1, sizeof(bool) * NUM_PHILOSOPHER);
    int index[NUM_PHILOSOPHER];
    for (int i = 0; i < NUM_PHILOSOPHER; i++) {
        index[i] = i;
    }

    pthread_t tids[NUM_PHILOSOPHER + 1];
    pthread_create(&tids[NUM_PHILOSOPHER], NULL, waiter, NULL);
    for (int i = 0; i < NUM_PHILOSOPHER; i++) {
        pthread_create(&tids[i], NULL, philosopher, (void*)&index[i]);
    }
    for (int i = 0; i < NUM_PHILOSOPHER; i++) {
        pthread_join(tids[i], NULL);
    }

    end_waiter();
    pthread_join(tids[NUM_PHILOSOPHER], NULL);

    pthread_mutex_destroy(&task_lock);
    sem_destroy(&task_reply_sem);
    sem_destroy(&task_request_sem);
    return 0;
}
